package q91_numDecodings;

public class Solution_2 {
    public static void main(String[] args) {

    }

    /**
     * 此题的解法意外的跟爬楼梯q70非常类似
     * 假设前i个字符串存在fi个解码方法
     * 那么实际上也有 fi = f(i - 1) + f(i - 2)
     * 但是这里加入了一些条件，比如说前置0则不能解码，数字大于26则不能解码两个字符等
     */
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 0; i < s.length(); i++) {

            // 如果没有前置0，则可以加入f(i - 1)
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            // 如果前两个字符没有前置0，并且不大于26, 可以加入f(i - 2)
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }


        }
        return f[n];
    }
}
